package _01_排序;
/*
    ◼ 堆排序可以认为是对选择排序的一种优化
    执行流程
    ① 对序列进行原地建堆（heapify） ② 重复执行以下操作，直到堆的元素数量为 1 ✓ 交换堆顶元素与尾元素
    ✓ 堆的元素数量减 1 ✓ 对 0 位置进行 1 次 siftDown 操作

    最好、最坏、平均时间复杂度：O(nlogn)，空间复杂度：O(1)，属于不稳定排序
*/
public class HeapSort03<E extends Comparable<E>> extends Sort<E>{
    private int heapSize; //堆元素个数
    @Override
    protected void sort() {
       heapSize = array.length;
       for(int i=(heapSize>>1)-1;i>=0;i--){
           siftDown(i);
       }
       while (heapSize>1){
           swap(0,--heapSize);
           siftDown(0);
       }
    }


    //下滤
    private void siftDown(int index){
        E element = array[index];
        int half = heapSize >> 1;
        while(index<half){
            int leftChildIndex = (index << 1)+1;
            E leftChildElement = array[leftChildIndex];

            int rightChildIndex = leftChildIndex + 1;
            if(rightChildIndex < heapSize && cmp(leftChildElement,array[rightChildIndex])<0){
                leftChildElement = array[leftChildIndex = rightChildIndex];
            }

            if(cmp(element,leftChildElement)>=0) break;

            array[index] = leftChildElement;
            index = leftChildIndex;
        }
        array[index] = element;
    }
}
